package zuosheng.Binarytree;

/**
 * @author lj
 * @Description: 莫瑞斯遍历二叉树
 * @date 2020-11-21 10:31
 * @QQ 851477108
 */


public class Morris {
    public class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            this.value = data;
        }
    }

    public void morris(Node head){
        if (head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            //如果cur有左子树
            if (mostRight != null){
                //找到cur左子树最右节点
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //从上面的while出来后,mostRight就是cur左子树上最右的节点
                //第一次来到必然左子树最右节点的右子树必空
                if (mostRight.right == null) {
                    mostRight.right = cur;//让其指向cur
                    cur = cur.left;//cur向左移动
                    //回到最外层的while,继续判断cur的情况
                    continue;//为了不执行cur = cur.right
                }else if(mostRight.right == cur) {//第二次来到节点mostRight.right是指向cur的
                    mostRight.right = null;//让其指向null
                }
            }
            //除了左子树最右节点的右子树为空的情况不让cur右移
            //1.没有左子树
            //2.左子树最右节点的右子树指向cur
            cur = cur.right;
        }
    }
}
